\documentclass{ctexart}

\usepackage{graphicx}
\usepackage{amsmath}
\usepackage{subfigure}

\title{图的模板类设计}



\author{赖心怡 \\  医学实验班(临床医学八年制) 3210100987}

\begin{document}

\maketitle

\section{项目设计思路}

图是由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为：$G=(V，E)$, 其中: $G$ 表示一个图，$V$ 是图 $G$ 中顶点的集合，$E$ 是图 $G$ 中顶点之间边的集合. 本项目同时实现邻接表和临界矩阵两种存储方式.

邻接矩阵图 \verb|MGraph| 设计基本思想: 用一个一维数组 \verb|vertex[]| 存储图中顶点的信息，用一个二维数组（称为邻接矩阵）\verb|edge[][]| 存储图中各顶点之间的邻接关系, \verb|edge[u][v] = w| 指从顶点 \verb|u| 到顶点 \verb|v|, 权重为 \verb|w| 的边.

邻接表图 \verb|ALGraph|设计基本思路: 定义边表节点 \verb|EdgeNode| 和基于边表节点构建 \verb|VertexNode|. 类实现中用一个一维边表节点数组 \verb|adjlist[]| 存储图中顶点信息. 每一个边表节点 \verb|u| 包含一个存储临接点 \verb|v| 信息和对应边权重 \verb|w| 的队列.

参考了 \verb|boost| 中 \verb|graph| 类中 \verb|VertexlistGraph| 和 \verb|EdgelistGraph| 的关系. 其他如课本中分类可分为有权图和无权图, 有向图和无向图等.

\section{测试说明}

在图初始化时,可以让用户指定存储方式, 输入"$l$"存储方式为邻接表, 输入"$m$" 存储方式为邻接矩阵; 如果用户没有指定, 则根据图的实际情况决定, 若满足 $E < V ^ {2}$, 其中 $E$ 为边数, $V$ 为顶点数, 按邻接表方式存储; 反之以邻接矩阵存储.利用成员函数 \verb|listVertexes()| 和 \verb|listEdges()| 列出全部节点和边, 可证明图正确构建.

\begin{figure}
        \centering
	\subfigure[用户指定存储方式]{\includegraphics[width = 6cm]{figure2.png}}
	\subfigure[用户未指定存储方式]{\includegraphics[width = 6cm]{figure3.png}}
	\caption{测试用例}
	\label{Figure 2}
\end{figure}

内存泄漏检查结果如下:
\begin{verbatim}
==9203== 
==9203== HEAP SUMMARY:
==9203==     in use at exit: 0 bytes in 0 blocks
==9203==   total heap usage: 3 allocs, 3 frees, 74,752 bytes allocated
==9203== 
==9203== All heap blocks were freed -- no leaks are possible
==9203== 
==9203== For counts of detected and suppressed errors, rerun with: -v
==9203== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)

\end{verbatim}
\end{document}

